//**********************************************************************************
// Klasse Tree(Baumstruktur) enthält den Baum mit seinen Knoten und seine Funktionen
//
//
//**********************************************************************************
package binarytree.model;

import javax.swing.DefaultListModel;

// *****************************************************
// Klasse : Tree zum Erzeugen des Baums
// Eingabe : Keine
// Rückgabe: Keine
// Ausgabe : Keine
// *****************************************************
public class Tree {

    // Variablentyp für Art der Sortierung 
    public enum SelectedOrder {

        INORDER, PREORDER, POSTORDER
    }
    // Baumwurzel
    private Node root;
    // Liste für Sortierung
    private final DefaultListModel<Integer> list;
    // Variable für Art der Sortierung    
    public SelectedOrder order = SelectedOrder.INORDER;
    // Statusvariable ob AVL-Baum existiert
    private boolean isAVL = false;

    // *****************************************************
    // Konstruktor
    // Eingabe : Keine
    // Rückgabe: Keine
    // Ausgabe : Keine
    // *****************************************************    
    public Tree() {
        // Wurzel null -> leerer Baum
        root = null;
        list = new DefaultListModel<>();
    }

    // Getter für Wurzel
    public Node getRoot() {
        return root;
    }

    // *****************************************************
    // Methode: Knoten einfügen
    // Eingabe : Knoten
    // Rückgabe: Keine
    // Ausgabe : Keine
    // *****************************************************    
    public void insert(Node node) {
        // keine Wurzel
        if (null == root) {
            // Knoten ist neue Wurzel
            root = node;
        } else {
            // füge Knoten unter der Wurzel ein
            insert(root, node);
        }
    }

    // *****************************************************
    // Methode: Knoten einfügen (überladen)
    // Eingabe : Knotenvater, Knotenkind 
    // Rückgabe: Keine
    // Ausgabe : Keine
    // *****************************************************
    public void insert(Node parent, Node child) {
        // Kindknoten links vom Vaterknoten einfügen
        if (child.data < parent.data) {
            if (null == parent.lS) {
                parent.lS = child;
            } else {
                insert(parent.lS, child);
            }
            // Kindknoten rechts vom Vaterknoten einfügen
        } else {
            if (null == parent.rS) {
                parent.rS = child;
            } else {
                insert(parent.rS, child);
            }
        }
    }

    // *****************************************************
    // Methode: Knoten löschen
    // Eingabe : Wert des zu löschenden Knoten
    // Rückgabe: Keine
    // Ausgabe : Keine
    // *****************************************************
    public void delete(int data) {
        // fange bei der Wurzel an zu löschen und baue Baum neu auf
        root = delete(data, root);
    }

    // *****************************************************
    // Methode: Knoten löschen (überladen)
    // Eingabe : Wert des zu löschenden Knoten, aktueller Knoten
    // Rückgabe: aktueller Knoten
    // Ausgabe : Keine
    // *****************************************************
    private Node delete(int data, Node node) {
        if (null != node) {
            // suche links im Baum weiter falls aktueller Knoten nicht der zu löschende ist
            if (data < node.data) {
                node.lS = delete(data, node.lS);
                // suche rechts im Baum weiter falls aktueller Knoten nicht der zu löschende ist
            } else if (data > node.data) {
                node.rS = delete(data, node.rS);
            } else {
                // Knoten gefunden
                // hat er kein linkes Kind
                if (!node.hasLS()) {
                    // dann wird er durch rechten Teilbaum ersetzt
                    return node.rS;
                    // hat er kein rechtes Kind
                } else if (!node.hasRS()) {
                    // dann wird er durch linken Teilbaum ersetzt
                    return node.lS;
                } else {
                    // hat er zwei Kinder, suche nächstegrößeren Knoten im rechten Teilbaum
                    // und ersetze ihn durch diesen
                    Node buffer = nextMaxNode(node.rS);
                    // vorausgesetzt der nächstgrößere Knoten ist nicht das rechte Kind,
                    // ersetze im nächstgrößere Knoten den rechten Knoten durch rechten des
                    // zu löschenden
                    if (buffer != node.rS) {
                        buffer.rS = node.rS;
                    }
                    // ersetze linkes Kind des nächstgrößeren Knoten, durch den alten
                    buffer.lS = node.lS;
                    // ersetzt alten Knoten durch den nächstgrößeren Knoten
                    node = buffer;
                }
            }
        }
        return node;
    }

    // *****************************************************
    // Methode: Suche nächstgrößeren Wert inOrder
    // Eingabe : aktueller Knoten
    // Rückgabe:  nächstgrößerer Knotenä
    // Ausgabe : Keine
    // *****************************************************
    private Node nextMaxNode(Node node) {
        Node current = node;
        Node before = null;
        // solange es noch links Kinder gibt
        while (current.hasLS()) {
            // merke alten Vaterknoten
            before = current;
            // gehe zu nächstem linken kind
            current = current.lS;
        }
        if (null != before) {
            // 
            before.lS = current.rS;
        }
        return current;
    }

    // *****************************************************
    // Methode: Wertigkeiten bestimmen
    // Eingabe : keine
    // Rückgabe: keine
    // Ausgabe : Keine
    // *****************************************************
    public void getValues() {
        if (null != root) {
            // rufe ab Wurzel auf
            getLevels(root);
        }
    }

    // *****************************************************
    // Methode: Wertigkeiten bestimmen (überladen)
    // Eingabe : aktueller Knoten
    // Rückgabe: Anzahl der Ebenen unter Knoten
    // Ausgabe : Keine
    // *****************************************************
    private int getLevels(Node node) {
        int levelsLeft = 0;
        int levelsRight = 0;
        // bestimme Wertigkeiten vom linken Teilbaum
        if (node.hasLS()) {
            levelsLeft = getLevels(node.lS);
        }
        // bestimme Wertigkeiten vom rechten Teilbaum
        if (node.hasRS()) {
            levelsRight = getLevels(node.rS);
        }
        // bestimme Wertigkeit des aktuellen Knoten aus Differenz der Anzahl der Ebenen links und rechts darunter
        node.value = levelsLeft - levelsRight;
        // gib Anzahl der Ebenen darunter zurück, je nach dem ob links oder recht mehr sind
        if (levelsLeft > levelsRight) {
            return levelsLeft + 1;
        } else {
            return levelsRight + 1;
        }
    }

    public void makeAVL() {
        root = makeAVL(root);
    }
    
    // *****************************************************
    // method  : order the tree via AVL
    // input   : node
    // return  : none
    // output  : none
    // ******************************************************
    public Node makeAVL(Node node) {
        //go to the latest node (recursive)
        if (node.hasRS()) {
            node.rS = makeAVL(node.rS);
            getValues();
        }
        if (node.hasLS()) {
            node.lS = makeAVL(node.lS);
            getValues();
        }

        //start rotations on node, if nodes value isnt between -2 and 2 (exclusive)
        if (node.value < -1) {
            if (node.rS.value != 1) {
                node = lRotation(node);
            } //value < -1 and its right son's value = 0 or -1 -> left rotation
            else {
                node = rlRotation(node);
            } //value < -1 and its right son's value = 1 -> right-left rotation
        } else if (node.value > 1) {
            if (node.lS.value != -1) {
                node = rRotation(node);
            } //value > 1 and its left son's value = 0 or 1 -> right rotation
            else {
                node = lrRotation(node);
            } //value > 1 and its left son's value = 1 -> left-right rotation
        }

        getValues();
        return node;
    }

    ;
 
 
    Node lRotation(Node node) {
        Node right;             // buffer for right son
        Node buffer;            // buffer for left son of the right son

        right = node.rS;        // buffer right son of node

        buffer = right.lS;      // buffer left son of the right son
        node.rS = null;         // delete right son
        right.lS = null;        // delete left son of the right son

        node.rS = buffer;       // set buffer as new right son
        right.lS = node;        // set left son of the right son as the rotating node
        return right;           // replace the rotating node with its old right son

    }

    ;
 
    Node rRotation(Node node) {
        Node left;              // buffer for left son
        Node buffer;            // buffer for right son of the left son

        left = node.lS;         // buffer left son of node

        buffer = left.rS;       // buffer right son of the left son
        node.lS = null;         // delete left son
        left.rS = null;         // delete right son of the left son

        node.lS = buffer;       // set buffer as new left son
        left.rS = node;         // set right son of the left son as the rotating node
        return left;            // replace the rotating node with its old left son
    }

    ;
 
    //first a right rotation on selected node's right son
    //than a left rotation on selected node
    Node rlRotation(Node node) {
        node.rS = rRotation(node.rS);
        node = lRotation(node);
        return node;
    }

    ;
 
    //first a left rotation on selected node's left son
    //than a right rotation on selected node
    Node lrRotation(Node node) {
        node.lS = lRotation(node.lS);
        node = rRotation(node);
        return node;
    }

    ;
    
    
   

    // *****************************************************
    // Methode : Durchlaufen des Baumes inOrder ( L-A-R )
    // Eingabe : Knoten ab dem tiefer gegangen wird
    // R�ckgabe: Keine
    // Ausgabe : Keine
    // *****************************************************	
    public void inOrder(Node node) {
        if (node.hasLS()) {
            inOrder(node.lS);
        }
        list.addElement(node.data);
        if (node.hasRS()) {
            inOrder(node.rS);
        }
    }

    // *****************************************************
    // Methode : Durchlaufen des Baumes preOrder ( A-L-R )
    // Eingabe : Knoten ab dem tiefer gegangen wird
    // R�ckgabe: Keine
    // Ausgabe : Keine
    // *****************************************************		
    public void preOrder(Node node) {
        list.addElement(node.data);
        if (node.hasLS()) {
            preOrder(node.lS);
        }
        if (node.hasRS()) {
            preOrder(node.rS);
        }
    }

    // *****************************************************
    // Methode : Durchlaufen des Baumes postOrder ( L-R-A)
    // Eingabe : Knoten ab dem tiefer gegangen wird
    // R�ckgabe: Keine
    // Ausgabe : Keine
    // *****************************************************		
    public void postOrder(Node node) {
        if (node.hasLS()) {
            postOrder(node.lS);
        }
        if (node.hasRS()) {
            postOrder(node.rS);
        }
        list.addElement(node.data);
    }

    // *****************************************************
    // Methode : lösche Baum
    // Eingabe : Knoten ab dem tiefer gegangen wird
    // R�ckgabe: Keine
    // Ausgabe : Keine
    // *****************************************************	
    public void clear() {
        root = null;
        list.clear();
    }

    // Getter für Liste	
    public DefaultListModel<Integer> getList() {
        return list;
    }

    // Setter für Sortierart
    public void setOrder(SelectedOrder order) {
        this.order = order;
    }

    // *****************************************************
    // Methode : Aufruf für Sortierung
    // Eingabe : Keine
    // R�ckgabe: Keine
    // Ausgabe : Keine
    // *****************************************************	
    public void OrderList() {
        // leere Liste
        list.clear();
        // rufe je nach gewählter Sortierart die entsprechende Sortierfunktion aufä
        if (null != root) {
            switch (order) {
                case INORDER:
                    inOrder(root);
                    break;
                case PREORDER:
                    preOrder(root);
                    break;
                case POSTORDER:
                    postOrder(root);
                    break;
                default:
                    inOrder(root);
                    break;
            }
        }

    }
}
